package com.woldier.algorithm.sort;

/**
 * description 堆排序
 *
 * @author: woldier wong
 * @date: 2023/12/27$ 16:46$
 */
public class HeapSort {

    public static void heapSort(int[] nums) {
        heapify(nums); //建堆
        //排序
        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, 0, i); //交换最大值
            down(nums, 0, i + 1);
        }
    }

    /**
     * description 建堆操作
     *
     * @return void
     * @author: woldier wong
     * @date: 2023/12/27 16:49
     */
    public static void heapify(int[] nums) {
        for (int i = nums.length / 2 - 1; i > 0; i--) {
            down(nums, i, nums.length);
        }
    }

    /**
     * description 大根堆下潜操作
     *
     * @param nums
     * @param parent
     * @param size
     * @return void
     * @author: woldier wong
     * @date: 2023/12/27 16:56
     */
    public static void down(int[] nums, int parent, int size) {

        while (true) {
            int max = parent;
            int left = parent * 2; //得到左右孩子
            int right = left + 1;
            if (left < size && nums[left] > max) {
                max = left;
            } else if (right < size && nums[right] > max) {
                max = right;

            }
            if (parent == max) { //没有发生了下潜
                break;
            }
            swap(nums, parent, max); //发生下潜, 做交换
            parent = max;
        }
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
